polynomials→399f
co\-effi\-cients→399
commutative ring with identity→399
ring→399
associative→399
commutative→399
distributes→399
degree→399
leading co\-effi\-cient→399
monic polynomial→399
multivariate polynomial→400
polynomial arithmetic modulo $m$→400
carrying→400
multiple-precision arithmetic→400
Brown,→401
Hyde,→401
Tague,→401
Collins→401
Hamblin,→401
Karatsuba→401
field→401
commutative ring with identity→401
rational numbers→401
fractions→401
complex numbers→401
real numbers→401
rational functions→401
quotient polynomial→402
remainder polynomial→402
synthetic division→402
mod→402
unique factorization domain→403f
unit→403
primes→403
reciprocal,→403
field→403
irreducible polynomial→403
multivariate polynomials→403
multiple→403
divisor→403
relatively prime→404
primitive→404
primitive polynomials modulo $p$→404
Gauss→404
Gauss, lemma about polynomials→404
content→405
primitive part→405
greatest common divisor→405
Euclid's algorithm for polynomials→405f
Stevin→405
Girard,→405
pseudo-division of polynomials→407f
commutative ring with identity→407
Euclid's algorithm, generalized→407f
rational arithmetic→409
subresultant algorithm→410f
Collins→410
Brown→410
Traub→410
Hadamard→414
resultant→415
Sylvester's determinant→415
van der Waerden→415
Blum→415
Sturm→416
roots of a polynomial→416
polynomial, roots of→416
determinant→416
Bareiss,→416
reverse of a polynomial→416
extended Euclid's algorithm→417f
analysis of algorithms→417
binary gcd algorithm→417
units→417
irreducible→417
primitive polynomials→417
Sylvester's matrix→417
Hadamard→418
Cohn→418
string polynomials→418
degree→418
noncommutative multiplication→418f
multivariate polynomials→418
free associative algebra→418
homogeneous polynomial→418
greatest common right divisor→419
least common left multiple→419
matrices, greatest common right divisor→419
accuracy of floating point→420
Sturm→420
Brown→420
rational function approximation→420
approximation, by rational functions→420
Euclid's algorithm→420
convergents→420
continued fraction→420
continuant→420
Berlekamp→420
derivative→421
Fermat→421
shift register→424
null space→425
matrix, determination of rank→425
rank of a matrix→425
reciprocal→427
Zassenhaus→428
Berlekamp→429
Moenck,→429
Distinct-degree factorization→429f
Golomb→430
Welch→430
Hales→430
Schwarz→430
Rabin→430
Cantor→430
Zassenhaus→430
factoring polynomials over the integers→431f
Newton→431
von Schubert→431
Cantor,→431
Kronecker→431
Vaughan,→433
cyclotomic polynomials→433
Hensel→433
reverse polynomial→434
logical ``and''→434
Musser,→434
Collins,→434
modular method for polynomial gcd→434f
greatest common divisors of polynomials→434f
Brown→435
Collins,→435
Moses→435f
Yun→435f
multivariate polynomials→436
Wang,→436
Musser→436
squarefree→436f
Berlekamp→436f
Chinese remainder theorem, for polynomials (exercise 3)→437
irreducible polynomials→437f
Mobius function→437
Lagrange→437
reciprocals→437
primitive root→437
Zassenhaus.→437
square root modulo $p$→437
primitive root→438
finite field→438
Galois field, see finite field→438
Eisenstein→438
multivariate polynomials→438
Hensel's Lemma→439
rational numbers→439
logical operations→439
distinct-degree factorization→439
proper factor→439
probabilistic algorithm→439
Cyclotomic polynomials→440
Mobius function→440
Squarefree factorization→440f
modular method→440
Yun→440
Collins→441
permutation→441
Pratt→441
evaluation of powers→441f
exponentiation→441f
powers, evaluation of→441f
binary number system→441
Pingala→441
Datta→441
Singh,→441
al-Uql\A \i dis\A \i →441
Saidan→441
Sachau→441
hardware→442
al-Kash\A \i →443
Egyptian→443
doubling,→443
halving,→443
Russian peasant method→443
Fateman,→443
factor method→443
power tree→444
Addition chains→444f
complexity of calculation→444f
optimum methods of computation, see complexity→444f
power tree→445
Dellac→445
de Jonqui\`eres→445
factor method→445
doubling→447
star step→447
small step→447
star chain→447
Fibonacci sequence→448
de Jonqui\`eres→449
Gioia,→449
Subbarao,→449
Sugunamma→449
carries→450
Thurber→451
Sch\"onhage→451
Brauer,→451
Erd\H os→451
Pr→453
Star chains→453f
Hansen→453f
multiset→454
Goulard,→458
de Jonqui\`eres→458
Thurber→458f
Thurber→459
Scholz→459f
Brauer→459f
directed graph→460f
ART ON REPRO REQUIRED→460
ART ON REPRO REQUIRED→461
source→461
sink→461
topologically sort→461
equivalent addition chains→461
ART ON REPRO REQUIRED→462
dual→462
SRB→462
JAE→462
octal→462
factor method→463
oriented binary tree→463
multiset→464f
prime factorization→464
fundamental theorem of arithmetic→464
gcd→464
lcm→464
Hansen→464f
Brauer→464
binary number system→464
square-root→464
Fibonacci number→464
Straus→464
monomial→464f
Sch\"onhage→465
addition-subtraction chain→465
Lehmer→465
Yao→465
Graham→465
Yao, Frances→465
dual→466
equivalent→466
Olivos→466f
factor method→466
Downey→466
Leong→466
Sethi→466
graph→466
vertex cover→466
Miller,→466
stability→466
Horner's rule→467f
Horner→467
Coolidge,→467
Newton→467
Whiteside,→467
complex number→467f
Fourier series→467f
Goertzel,→468
division of polynomials→468
parallel computations→469f
Estrin→469
Dorn→469
radix conversion→470f
Taylor→470
derivatives→470f
Horner→470
Shaw→470
Traub→470
stability→470
Adaptation of co\-effi\-cients→471f
sine→471
cosine→471
exponential function→471
precondition→471
Pan,→471
Motzkin→471
stability→471
Fike→472
register→472
Knuth,→472
Pan→473
Eve→474
Polynomial chains→475f
Ostrowski→475
von Mises→475
Motzkin→475
chain step→475
parameter step→475
result set→475
degrees of freedom→476f
Motzkin,→476
Belaga,→477
Strassen→478
Lipton→478
Schnorr,→478
Van de Wiele→478
Motzkin→478
Pan,→478
Borodin→479
Kohavi→479
Paz→479
Horner's rule→479
rational functions→479
continued fractions, with polynomials→479
Shaw→479
Traub→479
multivariate polynomials→479f
determinant→479f
modular arithmetic→480
division mod $p$→480
Hadamard's inequality→480
characteristic polynomial→480
Wilkinson,→480
permanent→480
Valiant→480
Turing machine→480
matrix multiplication→481f
inner product→481
Winograd→481
Strassen→481
Winograd→481
determinants→482
matrix inverses→482f
Bunch→482
Hopcroft,→482
Pan→482
Bini→482
Capovani→482
Lotti→482
Romani→482
Sch\"onhage→482
Pan→482
Winograd→482
Coppersmith→482
Brent→482
complex arithmetic→482
discrete Fourier transform→482f
Yates→483
Walsh transform→483
Walsh→483
Harmuth→483
Fast Fourier Transform→483f
parallel computation→484
Lagrange→484
interpolation→484f
Newton→485
Horner's rule→485
divided differences→485
Shamir→486
secret keys→486
cryptanalysis→486
Chinese remainder algorithm→486
Newton→486
mixed-radix representation→486
fast Fourier transforms→486
Horowitz,→486
Moenck→486
Borodin→486
Traub→486
Thiele→487
reciprocal differences→487
Milne-Thompson→487
Floyd,→487
Bilinear forms→487f
tensor→487f
multiplication of complex numbers→487
complex numbers→487
Matrix multiplication→487f
Fourier transforms→487
Normal evaluation scheme→487
rank of a tensor→488f
Hitchcock→488
Strassen,→488
Winograd→488
matrix multiplication→488f
transpose→488
Pan→488
Hopcroft→489
Musinski,→489
realization of a tensor→489
polynomials, multiplication of→489f
multiplication of polynomials→489f
Winograd→490f
Chinese remainder theorem→491
cyclic convolution→491f
convolution→491f
cyclotomic polynomial→492
Chinese remainder→492
partial fraction expansion→492
interpolation→492
Winograd→494f
Fourier transforms→494
fast Fourier transform→494
multiplication of polynomials→494f
companion matrix→494
cyclotomic polynomials→496
Winograd→496
multivariate polynomials→496
Ja'Ja',→496
Borodin→496
Munro→496
Horner's rule→496
de Jong→497
van Leeuwen→497
Shaw→497
Traub→497
factorial power→497
Ryser→497
permanent→497f
Fast Fourier transforms→497
FFT→497
divided difference→498
Newton→498
interpolation→498
adapted co\-effi\-cients→498f
FADD→498
FMUL→498
Pan→498
Eve→499
polynomial chain→499f
Horner's rule→499
degrees of freedom→499f
multivariate polynomials→499
van der Waerden→499
Blum→499
Motzkin→500f
rational functions→500
Pan→501
Horner's rule→501
complex numbers, multiplication of→501
Paterson→501
Stockmeyer→501
tensor→501f
rank→501f
bilinear forms→502f
Tarski→502
direct sum→502f
direct product→502f
Winograd→502f
matrix multiplication→502f
cyclic convolution→502f
Fourier transform→502
discrete Fourier transform→502
Strassen→503
quadratic forms→503
Nussbaumer→503
negacyclic convolution→503
Pan→503
trilinear representation→503
border rank→505
Pan→505
Winograd→505